Sakura Tears training 4 题解

A - Firefly's Queries

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;

void solve() {
    int n; cin >> n; int m; cin >> m;
    vector<ll> a(n), s(2 * n);
    for (int i = 0; i < n; i++) cin >> a[i];
    s[0] = a[0];
    for (int i = 1; i < n; i++) s[i] = s[i - 1] + a[i];
    for (int i = n; i < 2 * n; i++) s[i] = s[i - 1] + a[i - n];

    auto calc = [&] (int x) -> ll {
        if (x == -1) return 0;
        int cnt = (x + 1) / n;
        int rem = (x + 1) % n;
        ll ret = 0;
        ret += cnt * s[n - 1];
        ret += s[cnt + rem - 1] - (cnt - 1 < 0 ? 0 : s[cnt - 1]);
        return ret;
    };

    while (m--) {
        int l, r; cin >> l >> r; l--; r--;
        cout << calc(r) - calc(l - 1) << '\n';
    }
}

signed main() {
    freopen ("A.in", "r", stdin);
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

B - Sakurako's Task

Question

CF2008G Sakurako's Task

给定一个长度为 $n$ 的数组 ${a}$ ，可以进行无数次下列操作：

选择任意一个 $i, j (i \neq j)$ ，然后令 $a_{i} = a_{i} + a_{j}$ 或 $a_{i} = a_{i} - a_{j}$

求，要求操作后的 $m e x_{k}$ 最大

Solution

想要 $m e x_{k}$ 最大，那么肯定让 $a_{i}$ 越小越好，根据裴蜀定理，令 $g$ 为数组中数的 $gcd$ ，最后 $a_{i}$ 的值肯定是 $0, g, 2 g, 3 g, \dots$

所以 $m e x_{k}$ 就是其中的空位，可以用二分求得最后的答案，二分枚举一个答案 $x$ ，那么被占的位置的个数就是 $min (n, x / g + 1)$ ，没有被占领的位置就是 $x - min (n, x / g + 1)$ ，如果没有被占领的位置大于等于 $k - 1$ 个，说明 check 成功

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long

void solve() {
    int n, k; cin >> n >> k;
    int g = 0;
    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        g = __gcd(g, x);
    }

    if (n == 1) {
        cout << (k <= g ? k - 1 : k) << '\n';
        return ;
    }

    ll L = -1, R = 1e18;
    
    auto check = [&] (ll x) -> bool {
        ll cnt = 0;
        ll num = x / g + 1;
        cnt = x - min(n, num);
        return cnt >= k - 1;
    };


    while (L + 1 < R) {
        ll mid = (L + R) >> 1;
        if (check(mid)) R = mid;
        else L = mid;
    }
    cout << R << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

C - Yunli's Subarray Queries (easy version)

Question

Yunli's Subarray Queries (easy version)

给定一个长度为 $n$ 的数组 $b$ ，定义一个操作为：

令一个 $b_{i} = x$ ， $x$ 为任意整数

记 $f (b)$ 为需要执行最少次数，使得 $b$ 中至少存在长度为 $k$ 的连续子数组

Solution

这个好像是 easy 版，没什么思维难度

连续子数组的管用套路，定义 $c_{i} = b_{i} - i$

所以从 $[i, i + k - 1]$ 里面 $c_{i}$ 相同的值就能满足一个公差为 $1$ 的等差数列

所以需要维护 $[i, i + k - 1]$ 里面 $c_{i}$ 众数的个数，用一个滑动窗口 + 优先队列来维护即可

Code

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
typedef long long ll;

void solve() {
    int n, k, q; cin >> n >> k >> q;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<ll> ans(n + 1);
    vector<ll> b(n + 1);

    for (int i = 1; i <= n; i++) b[i] = a[i] - i;

    map<int, int> mp;
    priority_queue<pair<int, int>> pq;
    
    auto in = [&] (int x) {
        if (mp.find(x) == mp.end()) mp[x] = 1;
        else mp[x]++;
        pq.push({mp[x], x});
    };

    auto del = [&] (int x) {
        if (mp.find(x) == mp.end()) return ;
        if (mp[x] == 1) mp.erase(x);
        else mp[x]--, pq.push({mp[x], x});
    };


    auto get_max = [&] () -> int {
        while (mp[pq.top().second] != pq.top().first) pq.pop();
        return pq.top().first;
    };
    
    for (int i = 1; i <= k; i++) in(b[i]);
    ans[1] = k - get_max();

    for (int i = 2; i + k - 1 <= n; i++) {
        del(b[i - 1]);
        in(b[i + k - 1]);
        ans[i] = k - get_max();
    }

    while (q--) {
        int l, r; cin >> l >> r;
        cout << ans[l] << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

D - Sakurako's Test

Question

给定一个数组 ${a}$ ，一共有 $q$ 次询问，每次询问给出一个 $x$ ，可以执行以下操作任意次

若 $a_{i} \geq x$ ， $a_{i} = a_{i} - x$

每次询问求当前 $x$ 下，序列的中位数最小是多少

Solution

看到中位数就心酸

显然需要中位数最小，肯定是能减就减，所以最后 $a_{i}$ 肯定会变成 $a_{i} mod x$

先固定一个 $x$ ，如果直接去暴力计算会超时，考虑二分最后的答案 $m i d$ ，那么 $[0, m i d], [x, x + m i d], [2 x, 2 x + m i d] \dots$ 都是最后小于中位数的数

由于值域不是很大，这个部分可以用值域前缀和在 $O (\frac{max {a}}{x})$ 的时间复杂度内求出

每次去求 $x$ 在 $x$ 都非常小时会超时，所以记录 $a n s_{x}$ 为答案，最后询问的时候 $O (1)$ 回答就好了

Code

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, q; cin >> n >> q;
    vector<int> s(n + 1,0);
    int m = -1;
    for (int i = 1; i <= n; i++) {
        int x; cin >> x; m = max(m, x);
        s[x] += 1;
    }
    for (int i = 1; i <= n; i++) s[i] += s[i - 1];

    auto check = [&] (int x, int mid) -> bool {
        int ret = 0;
        for (int l = 0; l <= m; l += x) {
            int r = min(m, l + mid);
            ret += s[r] - (l == 0 ? 0 : s[l - 1]);
        }
        return ret >= n / 2 + 1;
    };

    vector<int> ans(n + 1);
    for (int x = 1; x <= n; x++) {
        int l = -1, r = x;
        while (l + 1 < r) {
            int mid = (l + r) >> 1;
            if (check(x, mid)) r = mid;
            else l = mid;
        }
        ans[x] = r;
    }

    while (q--) {
        int x; cin >> x;
        cout << ans[x] << ' ';
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

Summary

中位数，考虑二分中位数，然后去 check 小于 mid 的个数
多次询问一个答案可以记录下，然后 $O (1)$ 回答

E - Determine Winning Islands in Race

Question

CF1998D Determine Winning Islands in Race

Elsie 和 Bessie 在一个 $n$ 个岛屿上比赛，有 $n - 1$ 条主要桥梁，第 $i$ 条链接 $i$ 和 $i + 1$

有 $m$ 条备用桥梁，第 $i$ 条链接 $u_{i}$ 和 $v_{i}$

Bessie 从 $1$ 岛屿出发，能用主要桥梁和备用桥梁，Elsie 从 $s$ 岛屿出发，只能走主要桥梁

当一个奶牛从一个岛屿 $i$ 离开时，岛屿 $i$ 崩塌，求谁能先到达 $n$ 岛屿

Solution

Elsie 从 $s$ 出发，一路是 $s + 1, s + 2, s + 3, \dots$

所以 Bessie 只能通过备用桥梁超过 Elsie

先预处理出 $d i s [x]$ 表示 $1$ 到 $x$ 的最短路

对于一个 $u \to v$ 的备用桥梁，如果 Elsie 的起点在 $[u + 1, v - (d i s [v] + 1) - 1]$ ，那么 Bessie 可以通过这座桥梁超过 Elsie

如果不存在一个桥梁能超过，那么就 Elsie 赢了

多个区间取并集可以用线段树，或者构造差分数组来求

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int INF = 0x3f3f3f3f;

void solve() {
    int n, m; cin >> n >> m;
    vector<vector<int>> g(n + 1);
    vector<pair<int, int>> e;
    vector<int> dis(n + 1, INF);
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        e.push_back({u, v});
    }
    for (int i = 1; i + 1 <= n; i++) {
        g[i].push_back(i + 1);
    }
    dis[1] = 0; queue<int> q; q.push(1);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto v : g[u]) {
            if (dis[v] == INF) {
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
    }

    vector<int> pre(n + 10, 0);
    for (auto [u, v] : e) {
        int l = u + 1, r = v - dis[u] - 1 - 1;
        if (l > r) continue;
        pre[l]++; pre[r + 1]--;
    }

    int now = 0;
    for (int i = 1; i < n; i++) {
        now += pre[i];
        cout << (now == 0 ? "1" : "0");
    }
    cout << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

F - Level Up

Question

CF1997E Level Up

Monocarp 从等级 $1$ 开始游戏。他即将与 $n$ 只怪物进行战斗，按照从 $1$ 到 $n$ 的顺序。第 $i$ 只怪物的等级为 $a_{i}$

对于给定顺序中的每只怪物，Monocarp 的遭遇如下：

如果 Monocarp 的等级严格高于怪物的等级，则怪物会逃跑；
否则，Monocarp 会与怪物战斗。

在每次与怪物战斗 $k$ 次后，Monocarp 的等级会增加 $1$

给出 $q$ 个查询

$i x$ ：如果参数 $k$ 等于 $x$ ，Monocarp 是否会与第 $i$ 只怪物战斗（或者这只怪物会逃跑）

Solution

法一: 根号分治

可以说，根号分治非常强大

首先，肯定要把询问离线下来，按照 $k$ 分组

对于一个 $k$ 如果 $k \leq B$ 那么直接暴力跑就好了

如果 $k > B$ ，那么总的等级数不会超过 $\frac{n}{B}$ ，我们可以开 $\frac{n}{B}$ 个前缀和 $p r e [j] [i]$ 表示表示前 $i$ 个数中大于 $j$ 的数的个数

那么对于每个询问，假设我们现在的位置是 $p o s$ ，等级为 $n o w$ ，那么我们下一个升级的位置就是第一个满足 $p r e [j] [i] >= p r e [n o w] [p o s] + k$ 的位置，显然可以二分得出，这部分的时间复杂度是个调和计数，大约为 $O (n \log^{2} n)$

取 $B = 1000$ 可以通过此题

Code

#include <bits/stdc++.h>
using namespace std;

constexpr int M = 300, B = 1000;

void solve() {
    int n, q; cin >> n >> q;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<vector<int>> pre(M, vector<int>(n + 1, 0)); // pre[j][i] 表示前 i 个数中大于 j 的数的个数
    for (int j = 0; j < M; j++)
        for (int i = 1; i <= n; i++) 
            pre[j][i] = pre[j][i - 1] + (a[i] > j); 
    
    vector<vector<pair<int, int>>> ask(n + 1);
    vector<int> ans(q + 1, 0);
    for (int i = 1; i <= q; i++) {
        int id, k; cin >> id >> k;
        ask[k].push_back({id, i});
    }

    for (int k = 1; k <= n; k++) {
        if (ask[k].empty()) continue;
        sort(ask[k].begin(), ask[k].end());

        if (k <= B) {
            int now = 1, cnt = 0, it = 0;
            for (int i = 1; i <= n; i++) {
                while (it < ask[k].size() && ask[k][it].first == i) {
                    ans[ask[k][it].second] = a[i] >= now;
                    ++it;
                }
                if (a[i] >= now && ++cnt == k) ++now, cnt = 0;
            }
        }
        else {
            int pos = 0, now = 0, it = 0;
            while (pos <= n) {
                pos = lower_bound(pre[now].begin(), pre[now].end(), pre[now][pos] + k) - pre[now].begin();
                // 跳到第一个大于 pre[now][pos] + k 的位置
                now += 1;
                while (it < ask[k].size() && ask[k][it].first <= pos) {
                    ans[ask[k][it].second] = a[ask[k][it].first] >= now;
                    ++it;
                }
            }
        }
    }

    for (int i = 1; i <= q; i++) cout << (ans[i] ? "YES" : "NO") << "\n";
}

int main() {
    ios::sync_with_stdio(0);
    int T; T = 1;
    while (T--) solve();
    return 0;
}

G - Penacony

Question

CF1996G Penacony

有 $n$ 个房屋和 $n$ 条道路，形成一个环，所有道路都是双向的

存在 $m$ 对友谊关系， $a, b$ ，需要保证 $a, b$ 之间需要存在一条路径

求最小维护的道路数量

Solution

一眼异或哈希

对于一个路径 $a, b$ ，需要让 $a \to b$ 被标上一个记号， $b \to n \to 1 \to a$ 标记上另外一个记号

所以只需要把 $a, b$ 点异或上一个相同的随机数即可

为了防止撞，我还写了一个双哈希

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    srand(20040318);
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) {
        int n, m; cin >> n >> m;
        vector<int> a(n + 1, 0), b(n + 1, 0);
        for (int i = 1; i <= m; i++) {
            int u, v; cin >> u >> v;
            int hsh1 = rand() * rand(), hsh2 = rand() * rand();
            a[u] ^= hsh1; a[v] ^= hsh1;
            b[u] ^= hsh2; b[v] ^= hsh2;
        }
        map<pair<int, int>, int> mp;
        int now1 = 0, ans = 0, now2 = 0;
        for (int i = 1; i <= n; i++) {
            now1 ^= a[i]; now2 ^= b[i];
            mp[{now1, now2}] += 1;
            ans = max(ans, mp[{now1, now2}]);
        }
        cout << n - ans << '\n';
    }
    return 0;
}